package com.mamingchao.basic.tree;

import java.util.*;

/**
 * Created by mlamp on 2024/6/3.
 * 哔哩哔哩上的学习视频：https://www.bilibili.com/video/BV1Az4y1S7c7/?spm_id_from=333.337.search-card.all.click&vd_source=18c79f7f659e710262bc991deb15a3c6
 * 【爱学习的饲养员】
 * https://www.bilibili.com/video/BV13g41157hK/?spm_id_from=333.788.recommend_more_video.0&vd_source=55f277b153e6cb87ac10090987cdc378
 * [左老师在哔哩哔哩]
 * 字典树，也叫前缀树；这个是一个数据结构，而不是算法
 *
 *
 * [go,google,good,baidu,bay]
 *
 *                       root
 *                      g    b
 *                      o    a
 *                      o   i  y
 *                      g   d
 *                      l   u
 *                      e
 * 力扣练习题
 * 208题：Implement trie 实现Trie (insert, search, startwith)
 * 720题：Longest word in dictionary; 词典中最长的单词
 * 692题：Top frequent words ；前K个词频最高的单词
 *
 *
 * 现在做的是208题：实现一个trie
 */
public class Trie {

    private TrieNode root;
    public Trie(){
        root = new TrieNode();
    }


    public static void main(String[] args) {
//        final String pathword1 =

//        System.out.println(alpha == alpha1);
    }


    public TrieNode insert(String pathword, String valueword){

        // 想要插入一个valueword, 那么这个
        TrieNode goingToContectNodeAlreadyThere;

        for (int i = 0; i < pathword.length(); i++) {
            char alpha = pathword.charAt(i);

            // 第一步，现有的路径，是不是有能匹配上的
            Iterator<TrieNode> children = this.root.getChildren().iterator();
            //
            TrieNode child = null;
            while (children.hasNext() && i < pathword.length()){
                child = children.next();
                // 如果根节点的孩子有 pathword的第一个字符，顺藤摸瓜向下钻取
                if (alpha == child.nodeValue) {
                    // 往下钻
                    List<TrieNode> childrenList = child.getChildren();
                    if(Objects.nonNull(childrenList) && childrenList.size() > 0) {
                        children = childrenList.iterator();
                    }
                    i++;
                    alpha = pathword.charAt(i);
                    continue;
                }
            }

            // 第二步，如果能匹配的，都匹配上了，pathword 还有字符没挂完，创建这挂
            // TODO 还差一个 pathword 最后一个字符匹配完，value word 赋值的操作
            while (Objects.nonNull(child) && i < pathword.length()) {
                TrieNode newNode = new TrieNode(alpha);
                List<TrieNode> childrenList = child.getChildren();

                if(Objects.isNull(childrenList))
                    childrenList = Collections.emptyList();

                i++;
                alpha = pathword.charAt(i);
                childrenList.add(newNode);
                child = newNode;
            }

            child.setValueword(valueword);

        }

        return root;
    }

    /**
     * 处理为 已存在在数中的节点，拼接 child node；并返回这个child node
     * @param goingToAppendNodeAlreadyThere 在该node下面，新建 value为 alpha 的TrieNode
     * @param alpha 插入的node的字母值；为pathword其中的一个字母
     * @return 返回新插入的 node
     */
    private TrieNode append(TrieNode goingToAppendNodeAlreadyThere, char alpha){

        TrieNode node = new TrieNode(alpha);
        List<TrieNode> children = goingToAppendNodeAlreadyThere.getChildren();
        if (children == null || children.isEmpty()) {
            children = Collections.emptyList();
        }
        children.add(node);

        return node;
    }

    /**
     * 查询某个
     * @param pathword 路径上的单词
     * @return
     */
    public boolean search(String pathword){
        return true;
    }

    /**
     * 这里面，node 2 node的路线上，如果还有权重的话，是不是就能算出来每条path，的权重和优先级；也就是每个valueword的权重
     * @param prefix 单词的前缀；
     * @return 返回以前缀开头的所有的单词
     */
    public ArrayList<String> startwith(String prefix){
        return null;
    }

    public TrieNode getRoot() {
        return root;
    }

    /**
     * 前缀树的节点类
     * 包含 每个节点的字符值
     * 这个节点上是否有关键字；如果有关键字，说明字典树中包含 从root根节点到该node的这个路径 <--> 映射对应 这valueword
     * 所以，这里看，hash映射是 key -->hash函数 --> valueword
     * 字典树/前缀树 是一个字符一个字符的path对应；一条唯一的path，对应一个 valueword
     * hash映射有可能有冲突，但是 trie前缀树，不会有冲突
     * 但是 trie的时间复杂度 应该不比hash 好
     * 但是hash做不到 按照前缀 搜索出来一个 valueWord的列表
     * 如上面 startwith 方法注释所述， 如果按前缀搜索 valueword列表，trie可以实现按权重或者优先级，查询和返回 关键字
     *
     * 那岂不是，我自己实现一个搜索引擎
     */
    public class TrieNode{

        // 用来创建root节点使用
        public TrieNode(){
        }

        // 用来创建路由node使用(路径上的，不是关键节点)
        public TrieNode(char nodeValue){
            this.nodeValue = nodeValue;
        }

        // 用来创建关键node使用
        public TrieNode(char nodeValue, String valueword){
            this.nodeValue = nodeValue;
            this.valueword = valueword;
        }

        // 该节点上的字符
        private char nodeValue;
        // 该节点上挂的 关键词
        private String valueword;

        // 下一个node的指针
        private List<TrieNode> children;

        // 当前node的 下行的线条
        private List<TrieLine> nextLines;


        public boolean is(char alpha){
            boolean is = false;
            if (alpha == nodeValue) {
                is = true;
            }

            return is;
        }

        public char getNodeValue() {
            return nodeValue;
        }

        public void setNodeValue(char nodeValue) {
            this.nodeValue = nodeValue;
        }

        public String getValueword() {
            return valueword;
        }

        public void setValueword(String valueword) {
            this.valueword = valueword;
        }

        public List<TrieNode> getChildren() {
            return children;
        }

        public void setChildren(List<TrieNode> children) {
            this.children = children;
        }

        public List<TrieLine> getNextLines() {
            return nextLines;
        }

        public void setNextLines(List<TrieLine> nextLines) {
            this.nextLines = nextLines;
        }
    }

    /**
     * 字典树/前缀树 每个线条的权重
     */
    public class TrieLine{

        // 该线条的权重
        private int weight;

        // 线条起点node的指针
        private TrieNode pre;

        // 线条终点node的指针
        private TrieNode next;


        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public TrieNode getPre() {
            return pre;
        }

        public void setPre(TrieNode pre) {
            this.pre = pre;
        }

        public TrieNode getNext() {
            return next;
        }

        public void setNext(TrieNode next) {
            this.next = next;
        }
    }

}
